package problem0928

func minMalwareSpread(graph [][]int, initial []int) int {
	size := len(graph)

	infected := make([]bool, size)
	for _, i := range initial {
		infected[i] = true
	}

	seen := make([]bool, size)

	var dfs func(int) int
	// 返回 0 表示遇到了 infected 计算机
	dfs = func(i int) int {
		if infected[i] {
			return 0
		}
		count := 1 // 1 是代表了 i 本身
		seen[i] = true
		for j := 0; j < size; j++ {
			if seen[j] || graph[i][j] == 0 {
				continue
			}
			c := dfs(j)
			if c == 0 {
				// 深入过程中，遇到了 infected
				// 就把 i 标记为 infected，可以加快后续的步骤
				// 但需要同时标记 seen[i]=false
				// 因为 dfs 不会检查 seen[i]=true 的点是否已经感染。
				infected[i] = true
				seen[i] = false
				return 0
			}
			count += c
		}
		return count
	}

	maxCount := -1
	res := size

	for _, i := range initial {
		count := 0
		seen[i] = true
		for j := 0; j < size; j++ {
			if seen[j] || graph[i][j] == 0 {
				continue
			}
			count += dfs(j)
		}
		if (maxCount < count) ||
			(maxCount == count && res > i) {
			maxCount = count
			res = i
		}
	}

	return res
}
